28.1.2010

• Popište TS, který počítá funkci sčítání

• Ukažte, že $x^y$ je PRF (můžete předpokládat, že sčítání a násobení PRF jsou)

• Za pomoci některého problému, jehož těžkost jsme si ukazovali na přednášce, ukažte, že batoh je NP-uplný.

• Definujeme-li problém DNF-SAT jako problém splnitelnosti formule v disjunktivně normální formě (DNF), jaká je složitost tohoto problému? Je to NP-úplný nebo patří do P?